package sort;

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {

        int[] a={12,3,45,767,34,7,56,99,13,44};
        System.out.println(Arrays.toString(a));
        int[] newArr = mergeSort(a,0,a.length-1);
        System.out.println(Arrays.toString(newArr));
    }

    /**
     * @param a 原数组
     * @param start 需要被拆分的区间的起始元素下标
     * @param end  需要被拆分的区间的结束元素下标
     * @return  合并后的有序新数组
     */
    private static int[] mergeSort(int[] a,int start,int end){
        //为防止递归出现"死循环"，当end与start相等时，(发生在对长度为1的数组再拆分时)，不必再执行
        if (start>=end){
            //使用return返回当前片段的新数组
            return new int[]{a[start]};
        }
        //求数组需要被拆分的区间的中间点
        int mid = (start+end)/2;
        //创建2个新的数组，分别表示拆分之后的左侧区域和右侧区域
        int[] leftArr = mergeSort(a,start,mid);
        int[] rightArr = mergeSort(a,mid+1,end);
        //创建新的数组，用于存放合并后的有序结果
        int[] newArr = new int[leftArr.length+rightArr.length];
        //声明变量,l,r,n分别表示leftArr,rightArr,newArr的下标变量
        int l=0;
        int r=0;
        int n=0;
        //当leftArr和rightArr都没有遍历完成前，一直循环
        while (l<leftArr.length && r<rightArr.length){
//            //对比2个数组中的元素
//            if (leftArr[l]<=rightArr[r]){
//                //左侧数组的元素更小，将左侧数组的元素放到新数组中
//                newArr[n]=leftArr[l];
//                l++;
//            }else {
//                //右侧数组的元素更小，将右侧数组的元素放到新数组中
//                newArr[n]=rightArr[r];
//                r++;
//            }
//            n++;
            newArr[n++] = leftArr[l]<rightArr[r]?leftArr[l++] :rightArr[r++];
        }
        //如果左侧数组还有剩余，可直接一次全部填充到新数组中
        while (l<leftArr.length){
            newArr[n++]=leftArr[l++];
        }
        //如果右侧数组还有剩余，可直接一次全部填充到新数组中
        while (r<rightArr.length){
            newArr[n++]=rightArr[r++];
        }
        return newArr;
    }
}
